{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms\n",
    "\n",
    "An algorithm is a well-defined, complete, step-by-step description that performs a process in a finite amount of time and space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_69\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_69\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_69\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_69\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_69\">\n",
       "  <b>Sketch #69:</b><br/>\n",
       "  <canvas id=\"canvas_69\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_69\">\n",
       "  <button id=\"run_button_69\" onclick=\"startSketch('69');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_69\" onclick=\"pauseSketch('69');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_69\" onclick=\"setupSketch('69');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_69\" onclick=\"drawSketch('69');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #69 state:</b> <span id=\"state_69\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'void setup() {\\n    int[] heights = new int[100];\\n\\n    for (int i = 0; i < heights.length; i++) {\\n        heights[i] = int(random(500));\\n    }\\n\\n    int b = biggest(heights);\\n    int s = smallest(heights);\\n    \\n    printArray(heights);\\n\\n    println(\"Biggest: \" + b + \" Smallest: \" + s);\\n}\\n\\nint biggest(int[] arr) {\\n    // what goes here?\\n    int max = arr[0];\\n    for (int i = 1; i < arr.length; i++) {\\n        if (arr[i] > max) {\\n            max = arr[i];\\n        } \\n    }\\n    return max;\\n}\\n\\nint smallest(int[] arr) {\\n    int min = arr[0];\\n    for (int i=1; i < arr.length; i++) {\\n        if (arr[i] < min) {\\n            min = arr[i];\\n        }\\n    }\\n    return min;\\n}\\n\\nvoid printArray(int[] myarray) {\\n    print(\"[\");\\n    for (int i = 0; i < myarray.length; i++) {\\n        print(myarray[i]);\\n        if (i != myarray.length - 1) {\\n            print(\", \");\\n        }\\n    }\\n    println(\"]\");\\n}';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_69\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_69\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_69\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_69\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_69\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_69\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_69\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_69\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_69\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_69\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_69\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_69\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_69\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_69\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_69\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_69\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_69\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_69\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_69\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_69\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_69\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_69\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_69\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_69\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_69\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_69\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_69\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_69\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[167, 100, 12, 178, 282, 278, 236, 421, 395, 458, 446, 299, 11, 237, 460, 4, 467, 163, 303, 349, 111, 368, 320, 159, 56, 32, 384, 20, 176, 204, 25, 133, 322, 423, 4, 337, 212, 420, 471, 261, 139, 414, 311, 345, 320, 87, 137, 46, 415, 70, 67, 302, 419, 469, 209, 386, 90, 422, 249, 328, 288, 462, 92, 115, 354, 446, 312, 71, 381, 75, 21, 497, 52, 252, 190, 4, 404, 74, 177, 31, 180, 466, 270, 1, 144, 155, 183, 305, 227, 283, 365, 349, 205, 423, 320, 392, 140, 13, 216, 108]\n",
      "Biggest: 497 Smallest: 1\n",
      "[38, 378, 490, 364, 65, 247, 296, 474, 339, 124, 473, 159, 233, 111, 314, 0, 49, 495, 51, 318, 42, 29, 210, 427, 140, 241, 11, 138, 381, 122, 389, 345, 75, 381, 328, 398, 231, 360, 316, 455, 235, 217, 171, 200, 57, 129, 268, 36, 227, 485, 180, 342, 50, 62, 366, 101, 408, 399, 420, 423, 154, 200, 461, 415, 439, 417, 200, 380, 251, 420, 268, 329, 47, 169, 211, 211, 387, 252, 184, 172, 57, 374, 249, 236, 133, 13, 212, 477, 454, 413, 314, 334, 126, 425, 379, 250, 196, 178, 366, 109]\n",
      "Biggest: 495 Smallest: 0\n",
      "[420, 125, 499, 333, 234, 53, 89, 13, 208, 276, 108, 395, 73, 389, 422, 109, 61, 312, 35, 473, 169, 274, 68, 405, 336, 53, 121, 289, 465, 50, 498, 406, 160, 280, 202, 459, 73, 208, 281, 240, 388, 403, 110, 68, 173, 390, 89, 351, 42, 242, 165, 401, 121, 305, 476, 54, 120, 333, 417, 215, 476, 441, 152, 126, 313, 12, 447, 257, 288, 176, 4, 4, 91, 291, 50, 304, 141, 220, 145, 85, 187, 96, 222, 484, 216, 60, 190, 237, 348, 322, 99, 365, 337, 47, 409, 380, 485, 404, 27, 357]\n",
      "Biggest: 499 Smallest: 4\n"
     ]
    }
   ],
   "source": [
    "void setup() {\n",
    "    int[] heights = new int[100];\n",
    "\n",
    "    for (int i = 0; i < heights.length; i++) {\n",
    "        heights[i] = int(random(500));\n",
    "    }\n",
    "\n",
    "    int b = biggest(heights);\n",
    "    int s = smallest(heights);\n",
    "    \n",
    "    printArray(heights);\n",
    "\n",
    "    println(\"Biggest: \" + b + \" Smallest: \" + s);\n",
    "}\n",
    "\n",
    "int biggest(int[] arr) {\n",
    "    // what goes here?\n",
    "    int max = arr[0];\n",
    "    for (int i = 1; i < arr.length; i++) {\n",
    "        if (arr[i] > max) {\n",
    "            max = arr[i];\n",
    "        } \n",
    "    }\n",
    "    return max;\n",
    "}\n",
    "\n",
    "int smallest(int[] arr) {\n",
    "    int min = arr[0];\n",
    "    for (int i=1; i < arr.length; i++) {\n",
    "        if (arr[i] < min) {\n",
    "            min = arr[i];\n",
    "        }\n",
    "    }\n",
    "    return min;\n",
    "}\n",
    "\n",
    "void printArray(int[] myarray) {\n",
    "    print(\"[\");\n",
    "    for (int i = 0; i < myarray.length; i++) {\n",
    "        print(myarray[i]);\n",
    "        if (i != myarray.length - 1) {\n",
    "            print(\", \");\n",
    "        }\n",
    "    }\n",
    "    println(\"]\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting\n",
    "\n",
    "## Double Trouble\n",
    "\n",
    "Let's design a very bad (slow) algorithm for sorting numbers.\n",
    "\n",
    "The Double Trouble sort algorithm, stated very abstractly:\n",
    "\n",
    "```\n",
    "Compare all combinations of values at positions i and j:\n",
    "    Swap where item at i is greater than the item at j\n",
    "```\n",
    "\n",
    "The Squared sort algorithm, stated with more details about an implementation:\n",
    "\n",
    "```\n",
    "Starting at the first element and going to second-to-last item, call this i:\n",
    "   Starting at i + 1, and going to last item, call this j:\n",
    "       if the item at location i is greater than the item at location j:\n",
    "           Swap the items at i and j\n",
    "       end if\n",
    "   end j loop\n",
    "end i loop\n",
    "```\n",
    "\n",
    "An algorithm is not so specific that it requires that it be written in a computer language. However, it is specific enough that it can be written in a programming language. \n",
    "\n",
    "### Sidebar: swapping\n",
    "\n",
    "The problem with swapping: You can't do this to swap the values of x and y:\n",
    "\n",
    "```\n",
    "x = y;\n",
    "y = x;\n",
    "```\n",
    "\n",
    "Why not?\n",
    "\n",
    "Solution:\n",
    "\n",
    "```\n",
    "temp = x;\n",
    "x = y;\n",
    "y = temp;\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_71\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_71\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_71\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_71\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_71\">\n",
       "  <b>Sketch #71:</b><br/>\n",
       "  <canvas id=\"canvas_71\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_71\">\n",
       "  <button id=\"run_button_71\" onclick=\"startSketch('71');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_71\" onclick=\"pauseSketch('71');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_71\" onclick=\"setupSketch('71');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_71\" onclick=\"drawSketch('71');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #71 state:</b> <span id=\"state_71\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'int[] heights = new int[100];\\n\\nvoid setup() {\\n    for (int i = 0; i < 100; i++) {\\n        heights[i] = int(random(50));\\n    }\\n    printArray(heights);\\n    double_trouble_sort(heights);\\n    printArray(heights);\\n}\\n\\nvoid double_trouble_sort(int[] myarray) {\\n    for (int i = 0; i < myarray.length - 1; i++) {\\n        for (int j = i + 1; j < myarray.length; j++) {\\n            if (myarray[i] > myarray[j]) {\\n                // swap\\n                int temp = myarray[i];\\n                myarray[i] = myarray[j];\\n                myarray[j] = temp;\\n            }\\n        }\\n    }\\n}\\n\\nvoid printArray(int[] myarray) {\\n    print(\"[\");\\n    for (int i = 0; i < myarray.length; i++) {\\n        print(myarray[i]);\\n        if (i != myarray.length - 1) {\\n            print(\", \");\\n        }\\n    }\\n    println(\"]\");\\n}';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_71\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_71\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_71\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_71\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_71\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_71\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_71\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_71\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_71\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_71\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_71\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_71\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_71\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_71\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_71\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_71\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_71\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_71\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_71\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_71\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_71\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_71\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_71\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_71\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_71\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_71\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_71\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_71\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[33, 19, 24, 45, 11, 16, 4, 15, 33, 39, 7, 41, 25, 10, 15, 26, 42, 29, 35, 36, 17, 28, 13, 13, 2, 8, 38, 36, 19, 27, 10, 33, 12, 43, 47, 2, 5, 24, 35, 32, 42, 42, 3, 32, 29, 9, 23, 20, 44, 37, 8, 2, 44, 40, 37, 47, 9, 10, 24, 29, 45, 33, 34, 1, 17, 23, 46, 24, 40, 49, 22, 47, 22, 12, 36, 8, 39, 29, 19, 2, 28, 3, 16, 43, 26, 42, 30, 6, 48, 32, 19, 9, 47, 33, 19, 33, 28, 21, 33, 47]\n",
      "[1, 2, 2, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 12, 12, 13, 13, 15, 15, 16, 16, 17, 17, 19, 19, 19, 19, 19, 20, 21, 22, 22, 23, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 29, 29, 29, 30, 32, 32, 32, 33, 33, 33, 33, 33, 33, 33, 34, 35, 35, 36, 36, 36, 37, 37, 38, 39, 39, 40, 40, 41, 42, 42, 42, 42, 43, 43, 44, 44, 45, 45, 46, 47, 47, 47, 47, 47, 48, 49]\n",
      "[26, 38, 28, 28, 10, 49, 27, 12, 14, 17, 29, 45, 19, 22, 2, 11, 45, 16, 1, 26, 48, 44, 42, 18, 22, 5, 11, 38, 27, 37, 20, 36, 31, 45, 13, 26, 43, 38, 49, 46, 14, 14, 16, 36, 14, 13, 42, 26, 8, 6, 17, 43, 0, 12, 40, 39, 45, 45, 24, 0, 15, 31, 8, 39, 30, 15, 6, 48, 1, 45, 28, 4, 21, 22, 37, 14, 23, 8, 7, 48, 29, 35, 48, 20, 29, 37, 33, 25, 23, 4, 0, 43, 5, 37, 2, 22, 35, 43, 47, 20]\n",
      "[0, 0, 0, 1, 1, 2, 2, 4, 4, 5, 5, 6, 6, 7, 8, 8, 8, 10, 11, 11, 12, 12, 13, 13, 14, 14, 14, 14, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 20, 21, 22, 22, 22, 22, 23, 23, 24, 25, 26, 26, 26, 26, 27, 27, 28, 28, 28, 29, 29, 29, 30, 31, 31, 33, 35, 35, 36, 36, 37, 37, 37, 37, 38, 38, 38, 39, 39, 40, 42, 42, 43, 43, 43, 43, 44, 45, 45, 45, 45, 45, 45, 46, 47, 48, 48, 48, 48, 49, 49]\n",
      "[30, 23, 39, 47, 20, 43, 9, 7, 2, 45, 16, 9, 9, 33, 46, 7, 0, 16, 29, 42, 22, 5, 9, 8, 30, 38, 6, 48, 14, 31, 17, 8, 47, 39, 27, 7, 37, 34, 36, 10, 30, 18, 23, 35, 28, 44, 39, 14, 19, 13, 11, 25, 32, 34, 28, 33, 6, 0, 21, 34, 23, 9, 47, 3, 15, 45, 22, 33, 34, 48, 27, 4, 11, 38, 6, 6, 9, 49, 17, 4, 43, 48, 4, 20, 30, 32, 7, 17, 37, 47, 9, 8, 0, 25, 11, 15, 3, 30, 18, 34]\n",
      "[0, 0, 0, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 20, 20, 21, 22, 22, 23, 23, 23, 25, 25, 27, 27, 28, 28, 29, 30, 30, 30, 30, 30, 31, 32, 32, 33, 33, 33, 34, 34, 34, 34, 34, 35, 36, 37, 37, 38, 38, 39, 39, 39, 42, 43, 43, 44, 45, 45, 46, 47, 47, 47, 47, 48, 48, 48, 49]\n"
     ]
    }
   ],
   "source": [
    "int[] heights = new int[100];\n",
    "\n",
    "void setup() {\n",
    "    for (int i = 0; i < 100; i++) {\n",
    "        heights[i] = int(random(50));\n",
    "    }\n",
    "    printArray(heights);\n",
    "    double_trouble_sort(heights);\n",
    "    printArray(heights);\n",
    "}\n",
    "\n",
    "void double_trouble_sort(int[] myarray) {\n",
    "    for (int i = 0; i < myarray.length - 1; i++) {\n",
    "        for (int j = i + 1; j < myarray.length; j++) {\n",
    "            if (myarray[i] > myarray[j]) {\n",
    "                // swap\n",
    "                int temp = myarray[i];\n",
    "                myarray[i] = myarray[j];\n",
    "                myarray[j] = temp;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "void printArray(int[] myarray) {\n",
    "    print(\"[\");\n",
    "    for (int i = 0; i < myarray.length; i++) {\n",
    "        print(myarray[i]);\n",
    "        if (i != myarray.length - 1) {\n",
    "            print(\", \");\n",
    "        }\n",
    "    }\n",
    "    println(\"]\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using Double Trouble to Sort Colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_72\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_72\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_72\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_72\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_72\">\n",
       "  <b>Sketch #72:</b><br/>\n",
       "  <canvas id=\"canvas_72\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_72\">\n",
       "  <button id=\"run_button_72\" onclick=\"startSketch('72');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_72\" onclick=\"pauseSketch('72');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_72\" onclick=\"setupSketch('72');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_72\" onclick=\"drawSketch('72');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #72 state:</b> <span id=\"state_72\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'PImage pic;\\nint p;\\nPImage big;\\n\\nvoid setup() {\\n    size(500, 500);\\n    colorMode(HSB, 255);\\n    pic = createImage(25, 25, RGB); \\n    pic.loadPixels();\\n    for (int i=0; i < pic.pixels.length; i++) {\\n        pic.pixels[i] = color(random(255), 255, 255);\\n    }\\n    pic.updatePixels();\\n    p = 0;\\n    big = createImage(width, height, RGB);\\n}\\n\\nvoid double_trouble_sort(PImage pic) {\\n    // outer loop removed, so we can see the pixels sort!\\n    pic.loadPixels();\\n    for (int j=p + 1; j < pic.pixels.length; j++) {\\n        if (hue(pic.pixels[p]) > hue(pic.pixels[j])) {\\n            color temp = pic.pixels[p];\\n            pic.pixels[p] = pic.pixels[j];\\n            pic.pixels[j] = temp;\\n        }\\n    }\\n    pic.updatePixels();\\n}\\n\\nvoid draw() {\\n    background(0);\\n    double_trouble_sort(pic);\\n    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\\n    image(big, 0, 0);\\n    p++;\\n    if (p >= pic.pixels.length - 2) {\\n        noLoop();\\n        println(\"Done!\");\\n    }\\n}';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_72\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_72\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_72\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_72\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_72\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_72\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_72\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_72\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_72\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_72\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_72\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_72\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_72\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_72\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_72\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_72\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_72\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_72\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_72\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_72\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_72\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_72\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_72\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_72\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_72\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_72\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_72\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_72\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done!\n",
      "Done!\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "PImage pic;\n",
    "int p;\n",
    "PImage big;\n",
    "\n",
    "void setup() {\n",
    "    size(500, 500);\n",
    "    colorMode(HSB, 255);\n",
    "    pic = createImage(25, 25, RGB); \n",
    "    pic.loadPixels();\n",
    "    for (int i=0; i < pic.pixels.length; i++) {\n",
    "        pic.pixels[i] = color(random(255), 255, 255);\n",
    "    }\n",
    "    pic.updatePixels();\n",
    "    p = 0;\n",
    "    big = createImage(width, height, RGB);\n",
    "}\n",
    "\n",
    "void double_trouble_sort(PImage pic) {\n",
    "    // outer loop removed, so we can see the pixels sort!\n",
    "    pic.loadPixels();\n",
    "    for (int j=p + 1; j < pic.pixels.length; j++) {\n",
    "        if (hue(pic.pixels[p]) > hue(pic.pixels[j])) {\n",
    "            color temp = pic.pixels[p];\n",
    "            pic.pixels[p] = pic.pixels[j];\n",
    "            pic.pixels[j] = temp;\n",
    "        }\n",
    "    }\n",
    "    pic.updatePixels();\n",
    "}\n",
    "\n",
    "void draw() {\n",
    "    background(0);\n",
    "    double_trouble_sort(pic);\n",
    "    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\n",
    "    image(big, 0, 0);\n",
    "    p++;\n",
    "    if (p >= pic.pixels.length - 2) {\n",
    "        noLoop();\n",
    "        println(\"Done!\");\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bubble Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bubble sort is the name given to a simple, and somewhat interesting, sorting algorithm.\n",
    "\n",
    "The Bubblesort algorithm in abstract terms:\n",
    "\n",
    "```\n",
    "While not done:\n",
    "    Run through all items in a set, i:\n",
    "        if item i is greater than item i + 1:\n",
    "            Swap items i and i + 1\n",
    "    If no swaps were made on last sweep, you are done\n",
    "```\n",
    "\n",
    "The Bubblesort algorithm, with more implementation details:\n",
    "\n",
    "```\n",
    "Let stop be the length of the array\n",
    "While stop is not at the beginning:\n",
    "    Starting at the first element and going to stop - 1, call this i:\n",
    "       Let new_stop be the beginning position\n",
    "       if the item at location i is greater than the item at location i + 1:\n",
    "           swap the items at i and i + 1\n",
    "           Save i as new_stop\n",
    "       end if\n",
    "    Let stop be new_stop\n",
    "end while\n",
    "```\n",
    "\n",
    "And written in Java:\n",
    "\n",
    "```java\n",
    "void bubble_sort(int[] array) {\n",
    "    int stop = array.length;\n",
    "    int last_swap;\n",
    "    while (stop != 0) {\n",
    "        last_swap = 0;\n",
    "        for (int i = 0; i < stop - 1; i++) {\n",
    "            if (array[i] > array[i + 1]) {\n",
    "                color temp = array[i];\n",
    "                array[i] = array[i + 1];\n",
    "                array[i + 1] = temp;\n",
    "                last_swap = i + 1;\n",
    "            }\n",
    "        }\n",
    "        stop = last_swap;\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Buuble Sort on Colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_73\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_73\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_73\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_73\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_73\">\n",
       "  <b>Sketch #73:</b><br/>\n",
       "  <canvas id=\"canvas_73\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_73\">\n",
       "  <button id=\"run_button_73\" onclick=\"startSketch('73');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_73\" onclick=\"pauseSketch('73');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_73\" onclick=\"setupSketch('73');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_73\" onclick=\"drawSketch('73');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #73 state:</b> <span id=\"state_73\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'PImage pic;\\nPImage big;\\nint stop;\\n\\nvoid setup() {\\n    size(500, 500);\\n    colorMode(HSB, 255);\\n    pic = createImage(25, 25, RGB); \\n    pic.loadPixels();\\n    for (int i=0; i < pic.pixels.length; i++) {\\n        pic.pixels[i] = color(random(255), 255, 255);\\n    }\\n    pic.updatePixels();\\n    big = createImage(width, height, RGB);\\n    stop = pic.pixels.length;\\n}\\n\\nvoid bubble_sort(PImage pic) {\\n    pic.loadPixels();\\n    //int stop = pic.pixels.length;\\n    int last_swap;\\n    if (stop != 0) {\\n        last_swap = 0;\\n        for (int i = 0; i < stop - 1; i++) {\\n            if (hue(pic.pixels[i]) > hue(pic.pixels[i + 1])) {\\n                color temp = pic.pixels[i];\\n                pic.pixels[i] = pic.pixels[i + 1];\\n                pic.pixels[i + 1] = temp;\\n                last_swap = i + 1;\\n            }\\n        }\\n        stop = last_swap;\\n    } else {\\n        noLoop();\\n        println(\"Done!\");\\n    }\\n    pic.updatePixels();\\n}\\n\\nvoid draw() {\\n    background(0);\\n    bubble_sort(pic);\\n    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\\n    image(big, 0, 0);\\n}';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_73\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_73\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_73\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_73\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_73\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_73\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_73\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_73\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_73\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_73\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_73\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_73\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_73\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_73\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_73\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_73\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_73\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_73\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_73\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_73\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_73\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_73\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_73\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_73\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_73\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_73\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_73\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_73\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done!\n",
      "Done!\n",
      "Done!\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "PImage pic;\n",
    "PImage big;\n",
    "int stop;\n",
    "\n",
    "void setup() {\n",
    "    size(500, 500);\n",
    "    colorMode(HSB, 255);\n",
    "    pic = createImage(25, 25, RGB); \n",
    "    pic.loadPixels();\n",
    "    for (int i=0; i < pic.pixels.length; i++) {\n",
    "        pic.pixels[i] = color(random(255), 255, 255);\n",
    "    }\n",
    "    pic.updatePixels();\n",
    "    big = createImage(width, height, RGB);\n",
    "    stop = pic.pixels.length;\n",
    "}\n",
    "\n",
    "void bubble_sort(PImage pic) {\n",
    "    pic.loadPixels();\n",
    "    //int stop = pic.pixels.length;\n",
    "    int last_swap;\n",
    "    if (stop != 0) {\n",
    "        last_swap = 0;\n",
    "        for (int i = 0; i < stop - 1; i++) {\n",
    "            if (hue(pic.pixels[i]) > hue(pic.pixels[i + 1])) {\n",
    "                color temp = pic.pixels[i];\n",
    "                pic.pixels[i] = pic.pixels[i + 1];\n",
    "                pic.pixels[i + 1] = temp;\n",
    "                last_swap = i + 1;\n",
    "            }\n",
    "        }\n",
    "        stop = last_swap;\n",
    "    } else {\n",
    "        noLoop();\n",
    "        println(\"Done!\");\n",
    "    }\n",
    "    pic.updatePixels();\n",
    "}\n",
    "\n",
    "void draw() {\n",
    "    background(0);\n",
    "    bubble_sort(pic);\n",
    "    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\n",
    "    image(big, 0, 0);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Quick Sort\n",
    "\n",
    "The final algorithm that we will look at today is Quicksort. Quicksort represents a class of algorithms in computer science that capture the motto \"divide and conquer\".\n",
    "\n",
    "The Quicksort algorithm, at 30,000 feet (abstract view):\n",
    "\n",
    "```\n",
    "Pick a pivot value\n",
    "Break set of items into two parts:\n",
    "    first part is all less than the pivot value\n",
    "    second part is all greater than the pivot value\n",
    "Sort the first part\n",
    "Sort the second part\n",
    "```\n",
    "\n",
    "The Quicksort algorithm, with more implementation details:\n",
    "\n",
    "```\n",
    "Quicksort on start and end:\n",
    "    if start less than end:\n",
    "        Partition from start to end around p:\n",
    "        Quicksort on start and p - 1\n",
    "        Quicksort on p and end\n",
    "```\n",
    "\n",
    "The partition picks a point, \n",
    "\n",
    "```\n",
    "Partition from start to end:\n",
    "   Pick a pivot position, p, and pivot value\n",
    "   Partition array into:\n",
    "       those less than pivot value\n",
    "       pivot value\n",
    "       those less than pivot value\n",
    "   return partition\n",
    "```\n",
    "\n",
    "In Java, the main quicksort function looks like:\n",
    "\n",
    "```java\n",
    "void quicksort(int lo, int hi) {\n",
    "    if (lo < hi) {\n",
    "        int p = partition(lo, hi);\n",
    "        quicksort(lo, p - 1);\n",
    "        quicksort(p + 1, hi);\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "Here is the whole algorithm in code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_75\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_75\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_75\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_75\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_75\">\n",
       "  <b>Sketch #75:</b><br/>\n",
       "  <canvas id=\"canvas_75\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_75\">\n",
       "  <button id=\"run_button_75\" onclick=\"startSketch('75');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_75\" onclick=\"pauseSketch('75');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_75\" onclick=\"setupSketch('75');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_75\" onclick=\"drawSketch('75');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #75 state:</b> <span id=\"state_75\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'int [] array;\\n\\nvoid quicksort(int lo, int hi) {\\n    if (lo < hi) {\\n        int p = partition(lo, hi);\\n        quicksort(lo, p - 1);\\n        quicksort(p + 1, hi);\\n    }\\n}\\n\\nint partition(int lo, int hi) {\\n    int pivotIndex = choosePivot(lo, hi);\\n    int pivotValue = array[pivotIndex];\\n    // put the chosen pivot at array[hi]\\n    int tmp = array[pivotIndex];\\n    array[pivotIndex] = array[hi];\\n    array[hi] = tmp;\\n\\n    int storeIndex = lo;\\n    // Compare remaining array elements against pivotValue = array[hi]\\n    for (int i = lo; i <= hi - 1; i++)  {\\n        if (array[i] < pivotValue) {\\n            tmp = array[i];\\n            array[i] = array[storeIndex];\\n            array[storeIndex] = tmp;\\n            storeIndex = storeIndex + 1;\\n        }\\n    }\\n    tmp = array[hi];\\n    array[hi] = array[storeIndex];\\n    array[storeIndex] = tmp;\\n    return storeIndex;\\n}\\n\\nint choosePivot(int lo, int hi) {\\n    return ceil((hi + lo) / 2);\\n}\\n\\nvoid print_array() {\\n    for (int i = 0; i < array.length; i++) {\\n        print(\"\" + array[i] + \", \");\\n    }\\n    println(\"\");\\n}\\n\\nvoid setup() {\\n    println(\"-----------------------------------------------------------------\");\\n\\n    array = new int [1000];\\n    for (int i = 0; i < array.length; i++) {\\n        array[i] = int(random(array.length));\\n    }\\n\\n    println(\"Before sorting:\");\\n    if (array.length < 100)\\n        print_array();\\n\\n    int start = millis();\\n    quicksort(0, array.length - 1);\\n    int stop = millis();\\n    println(\"Quicksort took: \" + (stop - start) + \" ms\");\\n    if (array.length < 100)\\n        print_array();\\n}\\n';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_75\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_75\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_75\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_75\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_75\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_75\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_75\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_75\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_75\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_75\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_75\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_75\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_75\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_75\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_75\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_75\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_75\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_75\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_75\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_75\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_75\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_75\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_75\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_75\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_75\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_75\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_75\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_75\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------------------------------------------------\n",
      "Before sorting:\n",
      "Quicksort took: 1 ms\n",
      "-----------------------------------------------------------------\n",
      "Before sorting:\n",
      "Quicksort took: 1 ms\n",
      "-----------------------------------------------------------------\n",
      "Before sorting:\n",
      "Quicksort took: 2 ms\n"
     ]
    }
   ],
   "source": [
    "int [] array;\n",
    "\n",
    "void quicksort(int lo, int hi) {\n",
    "    if (lo < hi) {\n",
    "        int p = partition(lo, hi);\n",
    "        quicksort(lo, p - 1);\n",
    "        quicksort(p + 1, hi);\n",
    "    }\n",
    "}\n",
    "\n",
    "int partition(int lo, int hi) {\n",
    "    int pivotIndex = choosePivot(lo, hi);\n",
    "    int pivotValue = array[pivotIndex];\n",
    "    // put the chosen pivot at array[hi]\n",
    "    int tmp = array[pivotIndex];\n",
    "    array[pivotIndex] = array[hi];\n",
    "    array[hi] = tmp;\n",
    "\n",
    "    int storeIndex = lo;\n",
    "    // Compare remaining array elements against pivotValue = array[hi]\n",
    "    for (int i = lo; i <= hi - 1; i++)  {\n",
    "        counter++;\n",
    "        if (array[i] < pivotValue) {\n",
    "            swap++;\n",
    "            tmp = array[i];\n",
    "            array[i] = array[storeIndex];\n",
    "            array[storeIndex] = tmp;\n",
    "            storeIndex = storeIndex + 1;\n",
    "        }\n",
    "    }\n",
    "    tmp = array[hi];\n",
    "    array[hi] = array[storeIndex];\n",
    "    array[storeIndex] = tmp;\n",
    "    return storeIndex;\n",
    "}\n",
    "\n",
    "int choosePivot(int lo, int hi) {\n",
    "    return ceil((hi + lo) / 2);\n",
    "}\n",
    "\n",
    "void print_array() {\n",
    "    for (int i = 0; i < array.length; i++) {\n",
    "        print(\"\" + array[i] + \", \");\n",
    "    }\n",
    "    println(\"\");\n",
    "}\n",
    "\n",
    "void setup() {\n",
    "    println(\"-----------------------------------------------------------------\");\n",
    "\n",
    "    array = new int [1000];\n",
    "    for (int i = 0; i < array.length; i++) {\n",
    "        array[i] = int(random(array.length));\n",
    "    }\n",
    "\n",
    "    println(\"Before sorting:\");\n",
    "    if (array.length < 100)\n",
    "        print_array();\n",
    "\n",
    "    int start = millis();\n",
    "    quicksort(0, array.length - 1);\n",
    "    int stop = millis();\n",
    "    println(\"Quicksort took: \" + (stop - start) + \" ms\");\n",
    "    if (array.length < 100)\n",
    "        print_array();\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick Sort applied to Colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "        var component = document.getElementById(\"sketch_76\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"state_76\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        component = document.getElementById(\"controls_div_76\");\n",
       "        if (component != undefined)\n",
       "            component.remove();\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "            // FIXME: Stop all previously running versions (?)\n",
       "            var processingInstance = Processing.getInstanceById(\"canvas_76\");\n",
       "            if (processingInstance != undefined && processingInstance.isRunning())\n",
       "                processingInstance.noLoop();\n",
       "        });\n",
       "\n",
       "\n",
       "        var output_area = this;\n",
       "        // find my cell element\n",
       "        var cell_element = output_area.element.parents('.cell');\n",
       "        // which cell is it?\n",
       "        var cell_idx = Jupyter.notebook.get_cell_elements().index(cell_element);\n",
       "        // get the cell object\n",
       "        var cell = Jupyter.notebook.get_cell(cell_idx);\n",
       "\n",
       "        function jyp_print(cell, newline) {\n",
       "            return function(message) {\n",
       "                cell.get_callbacks().iopub.output({header: {\"msg_type\": \"stream\"},\n",
       "                                                   content: {text: message + newline,\n",
       "                                                             name: \"stdout\"}});\n",
       "            }\n",
       "        }\n",
       "        window.jyp_println = jyp_print(cell, \"\\n\");\n",
       "        window.jyp_print = jyp_print(cell, \"\");\n",
       "\n",
       "        require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function() {\n",
       "           Processing.logger.println = jyp_print(cell, \"\\n\");\n",
       "           Processing.logger.print = jyp_print(cell, \"\");\n",
       "        });\n",
       "\n",
       "\n",
       "        "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"canvas_div_76\">\n",
       "  <b>Sketch #76:</b><br/>\n",
       "  <canvas id=\"canvas_76\"></canvas><br/>\n",
       "</div>\n",
       "<div id=\"controls_div_76\">\n",
       "  <button id=\"run_button_76\" onclick=\"startSketch('76');\">\n",
       "    <i class=\"fa fa-play-circle-o\" style=\"size: 2em;\"></i>\n",
       "        Run\n",
       "  </button>\n",
       "  <button id=\"pause_button_76\" onclick=\"pauseSketch('76');\">\n",
       "    <i class=\"fa fa-pause\" style=\"size: 2em;\"></i>\n",
       "        Pause\n",
       "  </button>\n",
       "  <button id=\"setup_button_76\" onclick=\"setupSketch('76');\">\n",
       "    setup()\n",
       "  </button>\n",
       "  <button id=\"draw_button_76\" onclick=\"drawSketch('76');\">\n",
       "    draw()\n",
       "  </button>\n",
       "</div>\n",
       "<b>Sketch #76 state:</b> <span id=\"state_76\">Loading...</span><br/>\n",
       "<script>\n",
       "\n",
       "function change_button(button, disable) {\n",
       "    button.disabled = disable;\n",
       "    if (disable) {\n",
       "        button.style.color = \"grey\";\n",
       "    } else {\n",
       "        button.style.color = \"black\";\n",
       "    }\n",
       "}\n",
       "\n",
       "function startSketch(id) {\n",
       "    switchSketchState(id, true);\n",
       "}\n",
       "\n",
       "function pauseSketch(id) {\n",
       "    switchSketchState(id, false);\n",
       "}\n",
       "\n",
       "function drawSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Drawing...\";\n",
       "            try {\n",
       "                processingInstance.redraw();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Drawing... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No drawing() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function setupSketch(id) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (processingInstance != undefined) {\n",
       "        if (processingInstance.setup != undefined) {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"Setting up...\";\n",
       "            try {\n",
       "                processingInstance.setup();\n",
       "                document.getElementById(\"state_\" + id).innerHTML = \"Setting up... done! Paused.\";\n",
       "                document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "            } catch (e) {\n",
       "                processingInstance.println(e.toString());\n",
       "                document.getElementById(\"state_\" + id).innerHTML = e.toString();\n",
       "                document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "            }\n",
       "        } else {\n",
       "            document.getElementById(\"state_\" + id).innerHTML = \"No setup() function. Paused.\";\n",
       "            document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Error.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"red\";\n",
       "    }\n",
       "    change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "    change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "    change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "    change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "}\n",
       "\n",
       "function switchSketchState(id, on) {\n",
       "    var processingInstance = Processing.getInstanceById(\"canvas_\" + id);\n",
       "    if (on) {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Running...\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"green\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id),  true);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), true);\n",
       "        processingInstance.loop();  // call Processing loop() function\n",
       "    } else {\n",
       "        document.getElementById(\"state_\" + id).innerHTML = \"Paused.\";\n",
       "        document.getElementById(\"state_\" + id).style.color = \"blue\";\n",
       "        change_button(document.getElementById(\"run_button_\" + id), processingInstance.draw == undefined);\n",
       "        change_button(document.getElementById(\"pause_button_\" + id), true);\n",
       "        change_button(document.getElementById(\"setup_button_\" + id), processingInstance.setup == undefined);\n",
       "        change_button(document.getElementById(\"draw_button_\" + id), processingInstance.draw == undefined);\n",
       "        processingInstance.noLoop(); // stop animation, call noLoop()\n",
       "    }\n",
       "}\n",
       "\n",
       "require([window.location.protocol + \"//calysto.github.io/javascripts/processing/processing.js\"], function () {\n",
       "    var processingCode = 'PImage pic;\\nPImage big;\\n\\nvoid quicksort(int lo, int hi) {\\n    if (lo < hi) {\\n        int p = partition(lo, hi);\\n        quicksort(lo, p - 1);\\n        quicksort(p + 1, hi);\\n    }\\n}\\n\\nint partition(int lo, int hi) {\\n    int pivotIndex = choosePivot(lo, hi);\\n    int pivotValue = pic.pixels[pivotIndex];\\n    // put the chosen pivot at pic.pixels[hi]\\n    color tmp = pic.pixels[pivotIndex];\\n    pic.pixels[pivotIndex] = pic.pixels[hi];\\n    pic.pixels[hi] = tmp;\\n\\n    int storeIndex = lo;\\n    // Compare remaining array elements against pivotValue = pic.pixels[hi]\\n    for (int i = lo; i <= hi - 1; i++)  {\\n        if (hue(pic.pixels[i]) < hue(pivotValue)) {\\n            tmp = pic.pixels[i];\\n            pic.pixels[i] = pic.pixels[storeIndex];\\n            pic.pixels[storeIndex] = tmp;\\n            storeIndex = storeIndex + 1;\\n        }\\n    }\\n    tmp = pic.pixels[hi];\\n    pic.pixels[hi] = pic.pixels[storeIndex];\\n    pic.pixels[storeIndex] = tmp;\\n    return storeIndex;\\n}\\n\\nint choosePivot(int lo, int hi) {\\n    return ceil((hi + lo) / 2);\\n}\\n\\nvoid print_array() {\\n    for (int i = 0; i < pic.pixels.length; i++) {\\n        print(\"\" + pic.pixels[i] + \", \");\\n    }\\n    println(\"\");\\n}\\n\\nvoid draw() {\\n    background(0);\\n    quicksort(0,  pic.pixels.length - 1);\\n    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\\n    image(big, 0, 0);\\n}\\nvoid setup() {\\n    size(500, 500);\\n    colorMode(HSB, 255);\\n    pic = createImage(25, 25, RGB); \\n    pic.loadPixels();\\n    for (int i=0; i < pic.pixels.length; i++) {\\n        pic.pixels[i] = color(random(255), 255, 255);\\n    }\\n    pic.updatePixels();\\n    big = createImage(width, height, RGB);\\n}\\n';\n",
       "    var cc;\n",
       "    var processingInstance;\n",
       "    var has_error = false;\n",
       "\n",
       "    try {\n",
       "        cc = Processing.compile(processingCode);\n",
       "    } catch (e) {\n",
       "        console.log(e);\n",
       "        cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "        document.getElementById(\"state_76\").innerHTML = e.toString();\n",
       "        document.getElementById(\"state_76\").style.color = \"red\";\n",
       "        has_error = true;\n",
       "    }\n",
       "    if (cc != undefined) {\n",
       "        try {\n",
       "            processingInstance = new Processing(\"canvas_76\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "        } catch (e) {\n",
       "            console.log(e);\n",
       "            cc = Processing.compile(\"println('\" + e.toString() + \"');\");\n",
       "            document.getElementById(\"state_76\").innerHTML = e.toString();\n",
       "            document.getElementById(\"state_76\").style.color = \"red\";\n",
       "            processingInstance = new Processing(\"canvas_76\", cc);\n",
       "            processingInstance.println = window.jyp_println\n",
       "            has_error = true;\n",
       "        }\n",
       "    }\n",
       "    if (processingInstance != undefined) {\n",
       "        setTimeout(function () {\n",
       "            // Canvas:\n",
       "            if (processingInstance.externals.context === undefined) {\n",
       "                document.getElementById(\"canvas_div_76\").style.display = \"none\";\n",
       "            }\n",
       "        }, 100);\n",
       "        // Controls:\n",
       "        if (!(processingInstance.isRunning() && processingInstance.draw != undefined)) {\n",
       "            document.getElementById(\"controls_div_76\").style.display = \"none\";\n",
       "        }\n",
       "        if (processingInstance.draw != undefined) {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_76\").innerHTML = \"Running...\";\n",
       "                document.getElementById(\"state_76\").style.color = \"green\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_76\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_76\"), false);\n",
       "            change_button(document.getElementById(\"setup_button_76\"),  true);\n",
       "            change_button(document.getElementById(\"draw_button_76\"), true);\n",
       "        } else {\n",
       "            if (!has_error) {\n",
       "                document.getElementById(\"state_76\").innerHTML = \"Done.\";\n",
       "                document.getElementById(\"state_76\").style.color = \"blue\";\n",
       "            }\n",
       "            change_button(document.getElementById(\"run_button_76\"), true);\n",
       "            change_button(document.getElementById(\"pause_button_76\"), true);\n",
       "            change_button(document.getElementById(\"setup_button_76\"),  processingInstance.setup == undefined);\n",
       "            change_button(document.getElementById(\"draw_button_76\"), true);\n",
       "        }\n",
       "    } else {\n",
       "        document.getElementById(\"canvas_div_76\").style.display = \"none\";\n",
       "        document.getElementById(\"controls_div_76\").style.display = \"none\";\n",
       "        if (!has_error) {\n",
       "            document.getElementById(\"state_76\").innerHTML = \"Error.\";\n",
       "            document.getElementById(\"state_76\").style.color = \"red\";\n",
       "        }\n",
       "        change_button(document.getElementById(\"run_button_76\"), true);\n",
       "        change_button(document.getElementById(\"pause_button_76\"), true);\n",
       "        change_button(document.getElementById(\"setup_button_76\"),  true);\n",
       "        change_button(document.getElementById(\"draw_button_76\"), true);\n",
       "    }\n",
       "});\n",
       "\n",
       "</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done!\n",
      "Done!\n",
      "Done!\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "PImage pic;\n",
    "PImage big;\n",
    "\n",
    "void quicksort(int lo, int hi) {\n",
    "    if (lo < hi) {\n",
    "        int p = partition(lo, hi);\n",
    "        quicksort(lo, p - 1);\n",
    "        quicksort(p + 1, hi);\n",
    "    }\n",
    "}\n",
    "\n",
    "int partition(int lo, int hi) {\n",
    "    int pivotIndex = choosePivot(lo, hi);\n",
    "    int pivotValue = pic.pixels[pivotIndex];\n",
    "    // put the chosen pivot at pic.pixels[hi]\n",
    "    color tmp = pic.pixels[pivotIndex];\n",
    "    pic.pixels[pivotIndex] = pic.pixels[hi];\n",
    "    pic.pixels[hi] = tmp;\n",
    "\n",
    "    int storeIndex = lo;\n",
    "    // Compare remaining array elements against pivotValue = pic.pixels[hi]\n",
    "    for (int i = lo; i <= hi - 1; i++)  {\n",
    "        if (hue(pic.pixels[i]) < hue(pivotValue)) {\n",
    "            tmp = pic.pixels[i];\n",
    "            pic.pixels[i] = pic.pixels[storeIndex];\n",
    "            pic.pixels[storeIndex] = tmp;\n",
    "            storeIndex = storeIndex + 1;\n",
    "        }\n",
    "    }\n",
    "    tmp = pic.pixels[hi];\n",
    "    pic.pixels[hi] = pic.pixels[storeIndex];\n",
    "    pic.pixels[storeIndex] = tmp;\n",
    "    return storeIndex;\n",
    "}\n",
    "\n",
    "int choosePivot(int lo, int hi) {\n",
    "    return ceil((hi + lo) / 2);\n",
    "}\n",
    "\n",
    "void print_array() {\n",
    "    for (int i = 0; i < pic.pixels.length; i++) {\n",
    "        print(\"\" + pic.pixels[i] + \", \");\n",
    "    }\n",
    "    println(\"\");\n",
    "}\n",
    "\n",
    "void draw() {\n",
    "    background(0);\n",
    "    quicksort(0,  pic.pixels.length - 1);\n",
    "    big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);\n",
    "    image(big, 0, 0);\n",
    "}\n",
    "void setup() {\n",
    "    size(500, 500);\n",
    "    colorMode(HSB, 255);\n",
    "    pic = createImage(25, 25, RGB); \n",
    "    pic.loadPixels();\n",
    "    for (int i=0; i < pic.pixels.length; i++) {\n",
    "        pic.pixels[i] = color(random(255), 255, 255);\n",
    "    }\n",
    "    pic.updatePixels();\n",
    "    big = createImage(width, height, RGB);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Processing",
   "language": "java",
   "name": "calysto_processing"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "text/x-java",
    "version": 2
   },
   "file_extension": ".java",
   "mimetype": "text/x-java",
   "name": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}